package pers.tz.题目.leetcode;

import java.util.*;

/**
 * @author irony
 * @date 2024-03-13
 */
public class leetcode_0003_无重复字符的最长子串 {
//给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
//
// 示例 1:
//输入: s = "abcabcbb"
//输出: 3
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
//
// 示例 2:
//输入: s = "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
//
// 示例 3:
//输入: s = "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
//
// 提示：
// 0 <= s.length <= 5 * 10⁴
// s 由英文字母、数字、符号和空格组成

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("au"));
    }

    public static int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }

        char[] chars = s.toCharArray();
        // 每个ascii字符的位置
        int[] map = new int[256];
        Arrays.fill(map, -1); // 初始化为-1
        map[chars[0]] = 0; // 第一个字符的位置

        // 1. 当前字符距离相同字符的距离
        int p1 = 0;
        // 2. 上一个字符距离相同字符的距离
        int p2 = 0;

        int pre = 1; // 这里是从1开始

        int ans = 1; // p1 p2取最短

        // i也是从1开始
        for (int i = 1; i < s.length(); i++) {
            p1 = i - map[s.charAt(i)];
            p2 = pre + 1;

            int cur = Math.min(p1, p2); // 局部解
            pre = cur;

            ans = Math.max(cur, ans); // 全局解
            map[s.charAt(i)] = i;
        }

        return ans;
    }

}
